/* 动态单链表C语言实现 */
#include <stdio.h>
#include <stdlib.h>

constexpr int TRUE = 1;
constexpr int FALSE = 0;
constexpr int OK = 1;
constexpr int ERROR = 0;
constexpr int INFEASIBLE = -1;
constexpr int OVERFLOW = -2;

typedef int Status;							// 函数的返回类型
typedef int ElemType;						// 数据元素的类型
typedef int (*Compare)(ElemType, ElemType); // 比较函数的指针

typedef struct LNode{						// 提前声明
	ElemType data;
	struct LNode* next;
}LNode, *LinkList;

// 初始化(格式化)线性链表
static Status LinkList_Init(LinkList* L) {
	if (*L == NULL) {						// 空链表初始化
		*L = (LinkList)malloc(sizeof(LNode));
		if (*L != NULL) {
			(*L)->data = 0;					// 首元节点数据为链表长度
			(*L)->next = NULL;				// 头指针指向头节点 头节点的数据域存放链表长度
		}
		else exit(ERROR);
		return OK;
	}																	  
	else {									// 非空单链表也可以进行格式化
		(*L)->data = 0;
		LNode* tmp1 = (*L)->next;			// tmp1指向首元节点
		(*L)->next = NULL;
		while (tmp1 != NULL) {
			LNode* tmp2 = tmp1->next;		// tmp2指向tmp1的下一个节点
			free(tmp1);
			tmp1 = tmp2;
		}
		return OK;
	}
}

// 销毁回收线性链表
static Status LinkList_Destroy(LinkList L) {
	LinkList tmp1 = L;
	while (tmp1 != NULL) {
		LinkList tmp2 = tmp1->next;			// 保留next指针的值
		free(tmp1);
		tmp1 = tmp2;
	}
	return OK;
}

// 获取线性链表L中指定位序i的元素，并用指针e返回
static Status LinkList_GetElem(LinkList L, int i, ElemType* e) {
	if (i <= 0 || i > L->data) exit(INFEASIBLE);
	LNode* tmpN = (LNode*)malloc(sizeof(LNode));
	if (tmpN == NULL) exit(ERROR);
	else tmpN = L;
	for (int j = 0; j < i && tmpN != NULL; j++) {
		tmpN = tmpN->next;					// 单链表不是随机存取的数据结构
	}
	if (tmpN != NULL) *e = tmpN->data;
	else exit(ERROR);
	return OK;
}

// 在单链表L中的指定位序i插入内部数据为e的节点
static Status LinkList_Insert(LinkList L, int i, ElemType e) {
	if (L == NULL) exit(INFEASIBLE);
	if (i <= 0 || i > L->data + 1) exit(INFEASIBLE);
	LNode* tmp = L;							// tmp指向头节点
	for (int j = 0; j < i - 1; j++) {		// 让tmp指针指向第(i - 1)个节点
		tmp = tmp->next;
	}
	LNode* newnode = (LNode*)malloc(sizeof(LNode));
	if (newnode == NULL) exit(ERROR);
	newnode->data = e;
	newnode->next = tmp->next;
	tmp->next = newnode;
	L->data++;
	return OK;
}

// 在单链表L中删除指定位序i的节点 并用e返回被删除节点的数据
static Status LinkList_Delete(LinkList L, int i, ElemType* e) {
	if (i <= 0 || i > L->data) exit(OVERFLOW);
	LNode* p = L, * q = L->next;
	for (int j = 0; j < i - 1 && q != NULL; j++) {
		p = q;
		q = q->next;
	}
	if (q == NULL) exit(ERROR);
	p->next = q->next;
	e = &q->data;
	free(q);
	L->data--;
	return OK;
}

// 输出动态单链表中的数据
static Status LinkList_Print(LinkList L) {
	printf("<LinkList> [ ");
	LNode* p = L->next;
	while (p != NULL) {
		printf("%d", p->data);
		if (p->next == NULL) printf(" ");
		else printf(", ");
		p = p->next;
	}
	printf("]\tLength = %d\n\n", L->data);
	return OK;
}

// 寻找元素位序 (顺序查找L中符合"Compare类型"函数的第一个元素)
static int LinkList_LocateElem(LinkList L, ElemType e, Compare cmp) {
	int ans = 0;
	for (LNode* p = L->next; p != NULL; p = p->next) {
		ans++;
		if (cmp(p->data, e)) {
			return ans;
		}
	}
	exit(ERROR);
}

// 返回指定元素的前驱，如果元素存在并用pre_e指针返回，否则返回错误代码
static Status LinkList_PriorElem(LinkList L, ElemType e, LNode* pre_e) {
	for (LNode* p = L->next; p != NULL; p = p->next) {
		if (p->next->data == e) {
			pre_e = p;
			return OK;
		}
	}
	exit(ERROR);
}

// 返回指定元素的后继，如果元素存在并用next_e指针返回，否则返回错误代码
static Status LinkList_NextElem(LinkList L, ElemType e, LNode* next_e) {
	for (LNode* p = L->next; p != NULL; p = p->next) {
		if (p->data == e) {
			next_e = p->next;
			return OK;
		}
	}
	exit(ERROR);
}

// 有序合并两个已经升序排列的链表La和Lb 并用Lc返回新链表
		/* 问题：合并时无法处理重复的元素 */
static Status LinkList_MergeList(LinkList La, LinkList Lb, LinkList Lc) {
	LinkList_Init(&Lc);
	LNode* p1 = La->next, *p2 = Lb->next;
	while (p1 != NULL && p2 != NULL) {
		if (p1->data <= p2->data) {
			LinkList_Insert(Lc, Lc->data + 1, p1->data);
			p1 = p1->next;
		}
		else {
			LinkList_Insert(Lc, Lc->data + 1, p2->data);
			p2 = p2->next;					// 注意参数为 Lc->data + 1
		}
	}
	while (p1 != NULL) {
		LinkList_Insert(Lc, Lc->data + 1, p1->data);
		p1 = p1->next;						// 注意不要忘记了
	}
	while (p2 != NULL) {
		LinkList_Insert(Lc, Lc->data + 1, p2->data);
		p2 = p2->next;
	}
	return OK;
}

int main(void) {
    
	return 0;
}